#ifndef QUEUE_H
#define QUEUE_H

template <typename T>
struct QueueNode {
    T val;
    QueueNode *nxt;
};

template <typename T>
class Queue
{
public:
    Queue();
    Queue(const Queue &other);
    ~Queue();

    void Push(const T &val);
    void Pop();
    T Front() const;
    bool IsEmpty() const;

    Queue& operator=(const Queue &other);

    friend class Path;

private:
    QueueNode<T> *head, *tail;
};

template <typename T>
Queue<T>::Queue() {
    this->head = new QueueNode<T>();
    this->head->val = T();
    this->head->nxt = nullptr;
    this->tail = this->head;
}

template <typename T>
Queue<T>::Queue(const Queue<T> &other) {
    this->head = new QueueNode<T>();
    this->head->val = T();
    this->head->nxt = nullptr;
    this->tail = this->head;
    for (auto ptr = other.head; ptr->nxt != nullptr; ptr = ptr->nxt) {
        this->Push(ptr->nxt->val);
    }
}

template <typename T>
Queue<T>::~Queue() {
    for (auto ptr = this->head; ptr != nullptr; ) {
        auto tmp = ptr->nxt;
        delete ptr;
        ptr = tmp;
    }
}

template <typename T>
void Queue<T>::Push(const T &val) {
    QueueNode<T>* node = new QueueNode<T>;
    node->val = val;
    node->nxt = nullptr;
    this->tail->nxt = node;
    this->tail = node;
}

template <typename T>
void Queue<T>::Pop() {
    auto tmp = this->head->nxt;
    this->head->nxt = this->head->nxt->nxt;
    delete tmp;
    if (this->head->nxt == nullptr) {
        this->tail = this->head;
    }
}

template <typename T>
T Queue<T>::Front() const {
    return this->head->nxt->val;
}

template <typename T>
bool Queue<T>::IsEmpty() const {
    return this->head->nxt == nullptr;
}

template <typename T>
Queue<T>& Queue<T>::operator=(const Queue<T> &other) {
    this->head = new QueueNode<T>();
    this->head->val = T();
    this->head->nxt = nullptr;
    this->tail = this->head;
    for (auto ptr = other.head; ptr->nxt != nullptr; ptr = ptr->nxt) {
        this->Push(ptr->nxt->val);
    }
    return *this;
}

#endif // QUEUE_H
